package dynamic;

import java.util.Arrays;

public class LIS {
//this is good
  public static int LengthOfLIS(int a[])
  {
    if (a == null || a.length == 0) return -1;
    int dp[] = new int[a.length];
    
    for (int i = 0 ; i < dp.length ; i++)
      dp[i] = 1;
    
    for (int i = 0 ; i < dp.length ; i++) {
      for (int j = 0 ; j < i ; j++) {
        if (a[i] > a[j])
          dp[i] = Math.max(dp[i], dp[j] + 1);
        else
          dp[i] = dp[i];
      }
    }
    System.out.println(Arrays.toString(dp));
    return dp[dp.length - 1];
  }
  
  
  
  public static int ceilIndex(int[] a, int l, int r, int key){
    int m = 0;
    while(r-l > 1){
      m = l + (r-l)/2;
      if(a[m] >= key)
        r = m;
      else
        l = m;
    }
    return r;
  }
  
  public static int GetCeilIndex(int A[], int T[], int l, int r, int key) {
    int m;
  
    while( r - l > 1 ) {
       m = l + (r - l)/2;
       if( A[T[m]] >= key )
          r = m;
       else
          l = m;
    }
  
    return r;
 }
  
  public static int lisLength(int[] a){
    int n = a.length;
    int[] tailTable = new int[n];
    int len; //always point to empty slot
    
    tailTable[0]=a[0];
    len = 1;
    for(int i = 1;i < n;i++){
      if(a[i]<tailTable[0]){
        //new smallest element
        tailTable[0]=a[i];
      }else if(a[i] > tailTable[len-1]){
        //a[i] wants to extend largest subsequence
        tailTable[len++]=a[i];
      }else{
        //a[i] want to be current end candidate of an existing subsequence
        //it will replace ceil value in tailTable
        tailTable[ceilIndex(tailTable, -1, len-1, a[i])]=a[i];
      }
      
    }
    return len;
    
    
  }
  
  public static int lis(int[] a){
    int size = a.length;
    int[] tailIdx = new int[size];
    int[] prevIdx = new int[size];
    int len;
    
    tailIdx[0]=0;
    prevIdx[0]=-1;
    len = 1;
    for(int i = 1; i < size; i++){
      if(a[i]<a[tailIdx[0]]){
        tailIdx[0]=i;
      }else if(a[i] > a[tailIdx[len-1]]){
        prevIdx[i]=tailIdx[len-1];
        tailIdx[len++]=i;
      }else{
        int pos = GetCeilIndex(a, tailIdx, -1, len-1, a[i]);
        prevIdx[i]=tailIdx[pos-1];
        tailIdx[pos]=i;
      }
    }
    
    for(int i = tailIdx[len-1];i>=0;i=prevIdx[i]){
      System.out.print(a[i] + "\t");
    }
    return len;
    
  }  
  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] array = { 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15 };
    System.out.println(LengthOfLIS(array));
  }

}
